package com.hedl.practice.StudyAlgorithm.quick_sort;

import java.util.Arrays;

public class QuickSort {

    /**
     * 首先判断数组是否为空或长度为0，如果是则直接返回。
     * 选择一个基准元素pivot，通常是数组的中间元素。
     * 初始化左右指针i和j，分别指向数组的第一个元素和最后一个元素。
     * 使用while循环，循环条件为i小于等于j。
     * 在循环中，先从左往右找到第一个大于等于pivot的元素的下标i，再从右往左找到第一个小于等于pivot的元素的下标j，然后交换这两个元素的位置。
     * 然后将i指针向右移动一位，j指针向左移动一位。
     * 重复步骤5和6，直到i大于j。
     * 对基准元素左边的子数组和右边的子数组分别递归调用快速排序算法。
     * 重复步骤2到8，直到排序完成。
     * @param arr
     * @param left
     * @param right
     */
    public void quickSort(Integer[] arr, Integer left, Integer right) {
        if (arr == null || arr.length == 0 || left >= right) {
            return;
        }
        int pivot = arr[left + (right - left) / 2];
        int i = left, j = right;
        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }
            while (arr[j] > pivot) {
                j--;
            }
            if (i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }
        quickSort(arr, left, j);
        quickSort(arr, i, right);
    }

    public static void main(String[] args) {
        Integer [] arr = {333,123,743,683,679,235,975,235,245,644,654};
        new QuickSort().quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}
